\subsection{An $\rb{O(n^\epsilon), \log n}$-approximation algorithm}
\label{sec:approx}
Here we introduce an $\rb{O(n^\epsilon), \log n}$-approximation
algorithm for the $k$-gossip problem in the offline model. This means,
if the $k$-gossip problem can be solved on any $n$-node dynamic
network in $L$ rounds, then our algorithm will solve the $k$-gossip
problem on any dynamic network in $O(n^\epsilon L)$ rounds, assuming
each node is allowed to broadcast $O(\log n)$ tokens, instead of one,
in each round.  Our algorithm is an LP based one, which makes use of
the evolution graph defined earlier. The following is a
straightforward corollary of Lemma~\ref{lem:level.steiner}.

\begin{corollary}
\label{cor:level.steiner}
The $k$-gossip problem can be solved in $l$ rounds if $k$ directed
Steiner trees can be packed in the corresponding evolution graph,
where for each token, the root of its Steiner tree is a source node at
level 0, and the terminals are all the nodes at level $2l$.
\end{corollary}

Packing Steiner trees in general directed graphs is NP-hard to
approximate even within $\Omega(m^{1/3-\epsilon})$ for any
$\epsilon>0$ \cite{cheriyan+s:steiner}, where $m$ is the number of
edges in the graph. Thus, our algorithm focuses on solving Steiner
tree packing problem with relaxation on edge capacities, allowing the
capacity to blow up by a factor of $O(\log n)$. First, we write down
the LP for the Steiner tree packing problem (maximizing the number of
Steiner trees packed with respect to edge capacities). Let $\cal T$ be
the set of all possible Steiner trees, and $c_e$ be the capacity of
edge $e$. For each Steiner tree $T\in \cal T$, we associate a variable
$x_T$ with it. If $x_T=1$, then Steiner tree $T$ is in the optimal
solution; if $x_T=0$, it's not. After relaxing the integral
constraints on $x_T$'s, we have the following LP, referred to as $\cal
P$ henceforth. Let $F(\cal P)$ denote the optimal fractional solution
for $\cal P$.
\junk{
\begin{eqnarray*}
\max & \sum_{T\in \cal T} x_{T}\\
\mbox{s.t.}& \sum_{T:e\in T} x_{T} \le c_{e} \,\, \forall e\in E \\
 & x_{T} \ge 0 \,\, \forall T\in \cal T
\end{eqnarray*}
}
\[
\begin{array}{rrr}
\max & \sum_{T\in \cal T} x_{T} & \\
\mbox{s.t.} & \sum_{T:e\in T} x_{T} \le c_{e}  & \,\, \forall e\in E \\
 & x_{T} \ge 0  & \,\, \forall T\in \cal T
\end{array}
\]
\junk{
%%%%%%% begin junk %%%%%%%
\begin{eqnarray*}
\min & \sum_{e\in E} c_e y_e \\
\mbox{s.t.} & \sum_{e\in T} y_e \ge 1 \,\, \forall T\in \cal T \\
 & y_e \ge 0 \,\, \forall e\in E
\end{eqnarray*}
%%%%%%% end junk %%%%%%%
}

\junk{
%%%%%%% begin junk %%%%%%%
\begin{lemma}[\cite{jain+ms:steiner}]
\label{thm:approx-steiner}
There is an $\alpha$-approximation algorithm for the fractional
maximum Steiner tree packing problem if and only if there is an
$\alpha$-approximation algorithm for the minimum-weight Steiner tree
problem.
\end{lemma}
\textcolor{red}{Directed or undirected?}
Charikar et al. \cite{charikar+ccdgg:steiner} gives an
$O(n^\epsilon)$-approximation algorithm for the minimum-weight
directed Steiner tree problem. This together with Lemma
\ref{thm:approx-steiner} implies,
%%%%% end junk %%%%%%%
}

\begin{lemma}[\cite{cheriyan+s:steiner}]
\label{thm:approx-pack-steiner}
There is an $O(n^\epsilon)$-approximation algorithm for the fractional
maximum Steiner tree packing problem in directed graphs.
\end{lemma}

Let $L$ be the number of rounds that an optimal algorithm uses with
every node broadcasting at most one token per round. We give an
algorithm that takes $O(n^\epsilon L)$ rounds with every node
broadcasting $O(\log n)$ tokens per round. Thus ours is an
$\rb{O(n^\epsilon), O(\log n)}$ bicriteria approximation algorithm,
shown in Algorithm \ref{alg:approx}.
\begin{algorithm}[ht!]
\caption{$\rb{O(n^\epsilon), O(\log n)}$-approximation
  algorithm}
\label{alg:approx}
\begin{algorithmic}[1]
  \REQUIRE A sequence of communication graphs $G_1,G_2,\dots$
  \ENSURE Schedule to disseminate $k$ tokens.

  \medskip

  \STATE Initialize the set of Steiner trees ${\cal S} = \emptyset$.

  \FOR{$i = 1 \to 2n^\epsilon$}

  \STATE Find $L^*$ such that with the evolution graph $G$ constructed
  from level $0$ to level $2L^*$, the approximate value for $F(\cal
  P)$ is $k/n^{\epsilon}$. In this step, we use the algorithm of
  \cite{cheriyan+s:steiner} to approximate $F(\cal
  P)$. \label{alg.step:lp}

  \STATE Let $x^*_T$ be the value of the variable $x_T$ in the
  solution from step \ref{alg.step:lp}. The number of non-zero
  $x^*_T$'s is polynomial with respect to $k$. Using randomized
  rounding, with probability $x^*_T$ include $T$ in the solution,
  ${\cal S} = {\cal S} \cup \{T\}$. Otherwise, don't include
  $T$. \label{alg.step:round}

  \STATE Remove communication graphs $G_1,G_2,\dots,G_{L^*}$ from the
  sequence, and reduce the remaining graphs' indices by $L^*$.

  \ENDFOR

  \STATE Use Corollary \ref{cor:level.steiner} to convert the set of
  Steiner trees $\cal S$ into a token dissemination
  schedule. \label{alg.step:convert}
\end{algorithmic}
\end{algorithm}

\begin{theorem}
\label{thm:approx}
Algorithm \ref{alg:approx} achieves an $O(n^\epsilon)$ approximation
to the $k$-gossip problem while broadcasting $O(\log n)$ tokens per
round per node, with high probability.
\end{theorem}
\begin{proof}
We show the following three claims: (i) In Step
\ref{alg.step:convert}, $|{\cal S}| \ge k$ with probability at least
$1-1/e^{k/4}$. This is the correctness of Algorithm \ref{alg:approx},
saying it can find the schedule to disseminate all $k$ tokens. (ii)
The number of rounds in the schedule produced by Algorithm
\ref{alg:approx} is at most $O(n^\epsilon)$ times the optimal
one. (iii) In the token dissemination schedule, the number of tokens
sent over an edge is $O(\log n)$ in any round with high probability.

First, we prove claim (i). Let $X_i$ denote the sum of non-zero
$x^*_T$'s in iteration $i$. $X=\sum_{i=1}^{2n^\epsilon} X_i$. We know
$\expect{X_i} = k/n^{\epsilon}$. Thus, $\expect{X} = 2n^\epsilon
k/n^{\epsilon} = 2k$, which is the expected number of Steiner trees in
set $\cal S$. By Chernoff bound, we have 
\[\prob{X \le k} = \prob{X \le \rb{1-\frac{1}{2}}\expect{X}} \le e^{-\frac{\rb{1/2}^2 \expect{X}}{2}} = e^{-\frac{\rb{1/2}^2   \cdot 2k}{2}} = \frac{1}{e^{k/4}}\]
Thus, $|{\cal S}| \ge k$ with probability at least $1-1/e^{k/4}$ in
Step \ref{alg.step:convert}.

Next we prove claim (ii). Let $L$ denote the number of rounds needed
by an optimal algorithm. Since in Step \ref{alg.step:lp} we used the
$O(n^\epsilon)$-approximation algorithm in \cite{cheriyan+s:steiner}
to solve $F(\cal P)$, we know $L^* \le L$. There are $2n^\epsilon$
iterations. Thus, the number of rounds needed by Algorithm
\ref{alg:approx} is at most $2n^\epsilon L^* \le 2n^\epsilon L$, which
is an $O(n^\epsilon)$-approximation on the number of rounds.

Lastly we prove claim (iii). When Algorithm \ref{alg:approx} does
randomized rounding in Step \ref{alg.step:round}, some constraint
$\sum_{T:e\in T} x_{T} \le c_{e}$ in $\cal P$ may be violated. In the
evolution graph, $c_{e} = 1$. Let $Y$ denote the sum of $x^*_T$'s in
this constraint. We have $\expect{Y}\le c_e = 1$. By Chernoff bound,
\begin{eqnarray*}
\prob{Y\ge \expect{Y} + \log n} &=& \prob{Y \ge \rb{1+\frac{\log n}{\expect{Y}}} \expect{Y}} \\
 &\le& e^{-\expect{Y}\sqb{\rb{1+\frac{\log n}{\expect{Y}}} \ln \rb{1+\frac{\log n}{\expect{Y}}} - \frac{\log n}{\expect{Y}}}} \le \frac{1}{n^{\log\log n}} \\
\end{eqnarray*}
Thus, the number of tokens sent over a given edge is $O(\log n)$ with
probability at least $1-1/n^{\log\log n}$. Since there are only
polynomial number of edges, no edge will carry more than $O(\log n)$
tokens in a single round with high probability.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%
%% \cite{lau:steiner}
